import { checkArr } from "./util";




/**
 * 冒泡排序
 * 优化1: 已经排好序的数组，提前比较
 * 优化2: 后面的部分已经排好序了，之后比较就到其之前的一个位置就好了，较少比较的次数
 * e.g:  [8, 2, 1, 10, 3]
 * @param arr 
 */
export const bubbleSort = (arr: number[]) => {
    if (checkArr(arr)) return arr;
    /**
     * 交换数组的位置
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    /**
     * 比较两个元素的大小
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => {
        return l - r
    }

    let len = arr.length;
    
    // 循环比较，然后交换位置
    for (let i = 0; i < len; i++) {
        // 刚开始让第一个变为最大值
        let sorted = true,
            endTag = 0;
        for (let j = 0; j < len; j++) {
            // 如果前面比后面的大，交换位置
            if (compare(arr[j], arr[j + 1]) > 0) {
                sorted = false;
                swap(j, j + 1);
                endTag = j;
            }
        }
        // 内层for循环结束的时候，[endTag, len - 1]已经有序了, 只需要排前面的就好了
        len = endTag
        //! 重置i, i从-1, 下一次就变成了0
        i = -1;

        // 没有交换过, 说明数组是有序的
        if (sorted) {
            break
        }
    }
}

/**
 * 冒泡排序
 * 优化1: 已经排好序的数组，提前比较
 * e.g:  [8, 2, 1, 10, 3]
 * @param arr 
 */
export const bubbleSort2 = (arr: number[]) => {
    if (checkArr(arr)) return arr;
    /**
     * 交换数组的位置
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    /**
     * 比较两个元素的大小
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => {
        return l - r
    }

    const len = arr.length;

    // 循环比较，然后交换位置
    for (let i = 0; i < len; i++) {
        // 刚开始让第一个变为最大值
        let sorted = true
        for (let j = 0; j < len - i; j++) {
            // 如果前面比后面的大，交换位置
            if (compare(arr[j], arr[j + 1]) > 0) {
                sorted = false;
                swap(j, j + 1);
            }
        }
        // 没有交换过, 说明数组是有序的
        if (sorted) {
            break
        }
    }
}




/**
 * 冒泡排序
 * e.g:  [8, 2, 1, 10, 3]
 * @param arr 
 */
export const bubbleSort1 = (arr: number[]) => {
    if (checkArr(arr)) return arr;
    /**
     * 交换数组的位置
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    /**
     * 比较两个元素的大小
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => {
        return l - r
    }

    const len = arr.length;

    // 循环比较，然后交换位置
    for (let i = 0; i < len; i++) {
        // 刚开始让第一个变为最大值
        for (let j = 0; j < len - i; j++) {
            // 如果前面比后面的大，交换位置
            if (compare(arr[j], arr[j + 1]) > 0) {
                swap(j, j + 1);
            }
        }
    }
}


